package sort.memory;

import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 快速排序
 * @author：涂有
 * @date 2017年11月26日 下午8:49:17
 */
public class QuickSortMutilThread{
	
	static class Frame{
		int a[];
		int start, end, middle;
		
		public Frame(){}
		
		public Frame(int[] a, int start, int end, int middle) {
			super();
			this.a = a;
			this.start = start;
			this.end = end;
			this.middle = middle;
		}
	}
	
	public static int threaNumber = 4;
	public static ExecutorService service;
	public static LinkedBlockingQueue<Frame> queue = new LinkedBlockingQueue<>();
	
	public static void init(){
		service = Executors.newFixedThreadPool(threaNumber);
	}
	
	public static void close(){
		service.shutdown();
	}
	
	/**非递归快排
	 * @throws ExecutionException 
	 * @throws InterruptedException */
	public static void sort(int[] a) throws InterruptedException, ExecutionException{
		AtomicInteger count = new AtomicInteger(1);
		queue.offer(new Frame(a, 0, a.length - 1, a.length >> 1));
		while(true){
			Frame f = queue.take();
			if(f.a == null){
				break;
			}
			service.execute(() -> {
				int pivot = QuickSort.adjust(a, f.start - 1, f.end, f.middle);
				int pre = pivot - 1;
				int next = pivot + 1;
				if(f.start < pre && next < f.end){
					queue.add(new Frame(a, f.start, pre, (f.start + pre) >> 1));
					queue.add(new Frame(a, next, f.end, (next + f.end) >> 1));
					count.incrementAndGet();
				}else if(f.start < pre){
					queue.add(new Frame(a, f.start, pre, (f.start + pre) >> 1));
				}else if(next < f.end){
					queue.add(new Frame(a, next, f.end, (next + f.end) >> 1));
				}else{
					if(count.decrementAndGet() == 0){
						queue.add(new Frame());
					}
				}
			});
		}
	}
}
